#include <iostream>
#include <cstdio>
#include <cstdlib>

#include <assert.h>

#ifdef _OMP
#include <omp.h>
#endif

#include "Utils.h"
#include "Bae.h"

Bae::Bae(const Data data):data_(data)
{
	// A little trick which permits us not to make any transposition computations...
	if (data_.getM() <= data_.getN())
		compute_prefix_sum();
	else
	{
		cout << "warning: m > n => transposition !" << endl;
		compute_prefix_sum_trans();
	}
}

const Mat& Bae::getPrefixSum() const
{
	return sum_;
}


void Bae::dispPrefixSum()
{
	int m = data_.getM();
	int n = data_.getN();

	for (int i = 0; i < m; i ++)
	{
		for (int j = 0; j < n; j ++)
		{
			cout << sum_[i][j] << "\t";
		}
		cout << endl;
	}
}


void Bae::compute_prefix_sum_trans()
{
	const Mat & a = data_.getMat();

	int m = data_.getM();
	int n = data_.getN();

	Mat prefixSum(n + 1, Vect(m + 1,0));

	for (int i = 1; i < n + 1; i ++)
	{
		for (int j = 1; j < m + 1; j ++)
		{
			prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + a[j - 1][i - 1];
		}
	}

	// we permute m and n
	sum_ = prefixSum;
	m_ = n;
	n_ = m;
}

void Bae::compute_prefix_sum()
{
	const Mat & a = data_.getMat();

	int m = data_.getM();
	int n = data_.getN();

	Mat prefixSum(m + 1, Vect(n + 1, 0));

	//Pas nécessaire si on initalise avec le constructeur de vector<t_int>
//	for (int i = 0; i < n; i ++)
//		prefixSum[0][i] = 0;
//
//	for (int i = 0; i < m; i ++)
//		prefixSum[i][0] = 0;
	//#pragma omp parallel for schedule(static)
	for (int i = 1; i < m + 1; i ++)
	{
		for (int j = 1; j < n + 1; j ++)
		{
			prefixSum[i][j] = prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1] + a[i - 1][j - 1];
		}
	}

	sum_ = prefixSum;
	m_ = m;
	n_ = n;
}


void Bae::bae_algo(Result& result)
{
	int m = m_;
	int n = n_;

	result.sum = - 1 >> 31 ;

	#pragma omp parallel
        {
	Result my_result;
	my_result.sum = -1 >> 31;
	t_int j0 = 0;

	t_int M = 0;
	t_int cand = 0;
	Vect s(n + 1, 0);

	#pragma omp for schedule(static,20)
	for (int g = 1; g < m + 1; g ++)
	{
		for (int i = g; i < m + 1; i ++)
		{
			t_int min = 0;

			for (int j = 1; j < n + 1; j ++)
			{
				s[j] = sum_[i][j] - sum_[g - 1][j];
				cand = s[j] - min;

				if (cand > M)
				{
					M = cand;
					my_result.x0 = j0;
					my_result.y0 = g - 1;
					my_result.x1 = j - 1;
					my_result.y1 = i - 1;
				}

				if (s[j] < min)
				{
					j0 = j;
					min = s[j];
				}
//				M = MAX(M, cand);
//				min = MIN(min, s[j]);
			}
		}
	}

	my_result.sum = M;

	#pragma omp critical
        {
            if (my_result > result)
                result = my_result;
        }
        }
	// We swap the results if the matrix was transposed
	if (data_.getM() > data_.getN())
	{
		swap(result.x0, result.y0);
		swap(result.x1, result.y1);
	}
}


// Method which does not give that good result....
// a useless implementation which costs time !
void Bae::bae_algo_alternative(Result& result)
{
	const Mat & a = data_.getMat();

	int m = data_.getM();
	int n = data_.getN();

	t_int M = 0;
	t_int min = 0;
	Vect s(n + 1, 0);
	Mat r(m + 1, Vect(n + 1,0));
	t_int cand = 0;

	for (int g = 1; g < m + 1; g ++)
	{
		s.assign(n + 1 , (t_int) 0);

		for (int i = g; i < m + 1; i ++)
		{
			min = 0;
			for (int j = 1; j < m + 1; j ++)
			{
				r[i][j] =  r[i][j - 1] + a[i - 1][j - 1];
				s[j] = s[j] + r[i][j];
				cand = s[j] - min;
				M = MAX(M, cand);
				min = MIN(min, s[j]);
			}
		}
	}

	result.sum = M;
}
